#include<iostream>
#include<stdlib.h>
using namespace std;

void hill_sort(int* arr,int sz)
{
    int gap = sz;
    while (gap > 1)
    {
        gap=gap/2;
        for (int i = 0; i < sz - gap; i++)
        {
            int end = i;
            int temp = arr[end + gap];
            while (end >= 0)
            {
                if (arr[end] > temp)
                {
                    arr[end + gap] = arr[end];
                    end-=gap;
                }
                else
                {
                    break;
                }
            }
            arr[end + gap] = temp;
        }
    }
}

int main()
{
    int arr[10];
    srand((unsigned int)time(nullptr));
    for(int i=0;i<10;i++)
    {
        arr[i]=rand()%10;
    }
    hill_sort(arr,10);
    for(int i=0;i<10;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<"\n";
    return 0;
}